﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using VCSKicksCollection;

namespace DSA___semestralkaA___2
{
    class Dijkstra
    {
        public int cenaCesty = 0;
        public string Vysledky;
        public Mesto vychoziUzelCesty = null;
        List<Mesto> dijkstrovaCesta = new List<Mesto>();

        public Dijkstra()
        { 
        
        }

        public int vratOhodnoceniHrany(Graf<Mesto, Hrana<Mesto, int>> graf,Mesto start, Mesto konec)
        {
            return vratHranu(graf,start, konec).vratOhodnoceni();
        }

        public Hrana<Mesto, int> vratHranu(Graf<Mesto, Hrana<Mesto, int>> graf,Mesto start, Mesto konec)
        {
            foreach (var item in graf.vratSeznamHranVUzlu(start))
            {
                if (item.vratUzelA().getY() == konec.getY() && item.vratUzelA().getX() == konec.getX())
                {

                    //Console.WriteLine("Vracím hranu");
                    return item;
                }
            }

            foreach (var item in graf.vratSeznamHranVUzlu(konec))
            {
                if (item.vratUzelA().getY() == start.getY() && item.vratUzelA().getX() == start.getX())
                {

                    //Console.WriteLine("Vracím hranu");
                    return item;
                }

            }
            //Console.WriteLine("NIC");
            return default(Hrana<Mesto, int>);
        }

        public List<Mesto> DijkstraN(Graf<Mesto, Hrana<Mesto, int>> graf, Mesto startProhledavani)
        {

            Dictionary<Mesto, Mesto> predchoziVrchol = new Dictionary<Mesto, Mesto>(); //kvůli backtrakingu
            Dictionary<Mesto, int> vzdalenost = new Dictionary<Mesto, int>(); //pro výpočet nejkratší vzdálenosti
            PriorityQueue<Mesto> fronta = new PriorityQueue<Mesto>(); //hlavní struktura
            PriorityQueue<Mesto> nejblizsiPZS = new PriorityQueue<Mesto>();

            //inicializace
            foreach (Mesto item in graf)
            {
                predchoziVrchol.Add(item, null);
                if (!item.Equals(startProhledavani))
                { vzdalenost.Add(item, 100000); }
            }

            //vložím první vrchol do fronty a nastavím vzdálenost
            
                fronta.Enqueue(startProhledavani);
                vzdalenost[startProhledavani] = 0;
            



            Mesto mesto;
            Mesto konecna = null;
            //dělám, dokud ve frontě ještě něco je
            while (fronta.Count > 0)
            {

                //odeberu prioritní prvek z fronty
                mesto = fronta.Dequeue();

                //if (mesto.PZS == true) { nejblizsiPZS.Enqueue(mesto); break; }



                //prioritní vytahování incidentních hran
                //tady je potřeba udělat natahování do listu!!!!
                foreach (Hrana<Mesto, int> hrana in graf.vratSeznamHranVUzlu(mesto))
                {
                    //if (konecna != null) break;

                    //výběr opačného uzlu
                    Mesto prvni, druhy;
                    if (hrana.vratUzelA().getX() == mesto.getX())
                    {
                        prvni = (Mesto)hrana.vratUzelB();
                        druhy = (Mesto)hrana.vratUzelA();
                    }
                    else
                    {
                        prvni = (Mesto)hrana.vratUzelA();
                        druhy = (Mesto)hrana.vratUzelB();
                    }


                    int novaVzdalenost = vzdalenost[mesto] + vratOhodnoceniHrany(graf, prvni, druhy);
                    if (novaVzdalenost < vzdalenost[prvni])
                    {
                        vzdalenost[prvni] = novaVzdalenost;
                        prvni.Cena = novaVzdalenost;
                        predchoziVrchol[prvni] = mesto;
                        fronta.Enqueue(prvni);



                        //if (prvni.PZS == true) { nejblizsiPZS.Enqueue(prvni); }
                        //pokud je to pozemní záchranná pozemní stanice, tak končím
                    }


                }



                if (konecna == null)
                {
                    if (mesto.PZS == true) { konecna = mesto; break; }
                }
                else
                {
                    if (mesto.PZS == true && konecna.Cena > mesto.Cena) { konecna = mesto; break; }
                }


            }

            //konecna = nejblizsiPZS.Dequeue();

            string s = "";



            //tady bude traverzování
            //-- vyberu uzel s nejmenší hodnotou "konecna", který má PSZ
            //-- pak se vracím zpět


            if (konecna == null)
            { s += "Cesta nebyla nalezena pro bod: " + startProhledavani.NazevMesta; }
            else
            {
                cenaCesty = konecna.Cena;

                //backtracking -> uložení do listu
                string zz = konecna.ToString();
                Mesto tmp = konecna;
                List<Mesto> lp = new List<Mesto>();
                lp.Add(konecna);
                s += "Vyhledávám nejkratší cestu\r\n\r\n";
                if (cenaCesty == 0)
                {
                    s += "V tomto městě je záchranka";
                }
                else
                {

                    s += "Cena cesty: " + cenaCesty + "\r\n\r\n";

                }
                s += " -> " + konecna.getName();
                vychoziUzelCesty = konecna;


                while (startProhledavani != tmp)
                {
                    

                        tmp = predchoziVrchol[tmp];
                        lp.Add(tmp);
                        s += " -> " + tmp.getName();
                        vychoziUzelCesty = tmp;
                    

                }



                //výpis výsledku
                s += "\r\n\r\n";
                foreach (var item in predchoziVrchol)
                {
                    s += vzdalenost[item.Key] + " -> " + item.Key + " -> " + item.Value + "\r\n";
                }
                Vysledky = s;

                //vrátím cestu
                dijkstrovaCesta = lp;
                return dijkstrovaCesta;
            }

            //výpis výsledku pro případ, že nenajdu cestu
            s += "\r\n------------\r\n";
            foreach (var item in predchoziVrchol)
            {
                s += vzdalenost[item.Key] + " -> " + item.Key + " -> " + item.Value + "\r\n";
                dijkstrovaCesta.Remove(item.Key);
            }
            Vysledky = s;
            return dijkstrovaCesta;

        }




        //přetížený dijkstra
        public List<Mesto> DijkstraN(Graf<Mesto, Hrana<Mesto, int>> graf, Mesto startProhledavani, Mesto startProhledavani2, int pomer1, int pomer2)
        {

            Dictionary<Mesto, Mesto> predchoziVrchol = new Dictionary<Mesto, Mesto>(); //kvůli backtrakingu
            Dictionary<Mesto, int> vzdalenost = new Dictionary<Mesto, int>(); //pro výpočet nejkratší vzdálenosti
            PriorityQueue<Mesto> fronta = new PriorityQueue<Mesto>(); //hlavní struktura
            PriorityQueue<Mesto> nejblizsiPZS = new PriorityQueue<Mesto>();

            //inicializace
            foreach (Mesto item in graf)
            {
                predchoziVrchol.Add(item, null);
                if (!item.Equals(startProhledavani) || !item.Equals(startProhledavani2))
                { vzdalenost.Add(item, 100000); }
            }

            //vložím první vrchol do fronty a nastavím vzdálenost
            if (startProhledavani2 == null)
            {
                fronta.Enqueue(startProhledavani);
                vzdalenost[startProhledavani] = 0;
            }
            else
            {
                startProhledavani.Cena = pomer1;
                fronta.Enqueue(startProhledavani);
                vzdalenost[startProhledavani] = pomer1;

                startProhledavani2.Cena = pomer2;
                fronta.Enqueue(startProhledavani2);
                vzdalenost[startProhledavani2] = pomer2;
            }



            Mesto mesto;
            Mesto konecna = null;
            //dělám, dokud ve frontě ještě něco je
            while (fronta.Count > 0)
            {

                //odeberu prioritní prvek z fronty
                mesto = fronta.Dequeue();

                //if (mesto.PZS == true) { nejblizsiPZS.Enqueue(mesto); break; }



                //prioritní vytahování incidentních hran
                //tady je potřeba udělat natahování do listu!!!!
                foreach (Hrana<Mesto, int> hrana in graf.vratSeznamHranVUzlu(mesto))
                {
                    //if (konecna != null) break;

                    //výběr opačného uzlu
                    Mesto prvni, druhy;
                    if (hrana.vratUzelA().getX() == mesto.getX())
                    {
                        prvni = (Mesto)hrana.vratUzelB();
                        druhy = (Mesto)hrana.vratUzelA();
                    }
                    else
                    {
                        prvni = (Mesto)hrana.vratUzelA();
                        druhy = (Mesto)hrana.vratUzelB();
                    }


                    int novaVzdalenost = vzdalenost[mesto] + vratOhodnoceniHrany(graf, prvni, druhy);
                    if (novaVzdalenost < vzdalenost[prvni])
                    {
                        vzdalenost[prvni] = novaVzdalenost;
                        prvni.Cena = novaVzdalenost;
                        predchoziVrchol[prvni] = mesto;
                        fronta.Enqueue(prvni);



                        //if (prvni.PZS == true) { nejblizsiPZS.Enqueue(prvni); }
                        //pokud je to pozemní záchranná pozemní stanice, tak končím
                    }


                }



                if (konecna == null)
                {
                    if (mesto.PZS == true) { konecna = mesto; break; }
                }
                else
                {
                    if (mesto.PZS == true && konecna.Cena > mesto.Cena) { konecna = mesto; break; }
                }


            }

            //konecna = nejblizsiPZS.Dequeue();

            string s = "";



            //tady bude traverzování
            //-- vyberu uzel s nejmenší hodnotou "konecna", který má PSZ
            //-- pak se vracím zpět


            if (konecna == null)
            { s += "Cesta nebyla nalezena pro bod: " + startProhledavani.NazevMesta; }
            else
            {
                cenaCesty = konecna.Cena;

                //backtracking -> uložení do listu
                string zz = konecna.ToString();
                Mesto tmp = konecna;
                List<Mesto> lp = new List<Mesto>();
                lp.Add(konecna);
                s += "Vyhledávám nejkratší cestu\r\n\r\n";
                if (cenaCesty == 0)
                {
                    s += "V tomto městě je záchranka";
                }
                else
                {

                    s += "Cena cesty: " + cenaCesty + "\r\n\r\n";

                }
                s += " -> " + konecna.getName();
                vychoziUzelCesty = konecna;


                while (startProhledavani != tmp)
                {
                    if (startProhledavani2 == tmp)
                    {
                        break;
                    }
                    else
                    {

                        tmp = predchoziVrchol[tmp];
                        lp.Add(tmp);
                        s += " -> " + tmp.getName();
                        vychoziUzelCesty = tmp;
                    }

                }



                //výpis výsledku
                s += "\r\n\r\n";
                foreach (var item in predchoziVrchol)
                {
                    s += vzdalenost[item.Key] + " -> " + item.Key + " -> " + item.Value + "\r\n";
                }
                Vysledky = s;

                //vrátím cestu
                dijkstrovaCesta = lp;
                return dijkstrovaCesta;
            }

            //výpis výsledku pro případ, že nenajdu cestu
            s += "\r\n------------\r\n";
            foreach (var item in predchoziVrchol)
            {
                s += vzdalenost[item.Key] + " -> " + item.Key + " -> " + item.Value + "\r\n";
                dijkstrovaCesta.Remove(item.Key);
            }
            Vysledky = s;
            return dijkstrovaCesta;

        }


    }
}
